package org.example.BinaryTree;

public class Merge_binary_trees {
    public static void main(String[] args) {
        //合并二叉树

        //给你两棵二叉树： root1 和 root2 。
        //想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
        //返回合并后的二叉树。
        //注意: 合并过程必须从两个树的根节点开始。
        TreeNode root1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);
        root1.left = node3;
        root1.right = node2;
        node3.left = node5;
        TreeNode root2 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);
        root2.left = node7;
        root2.right = node8;
        node7.right = node9;
        node8.right = node10;
        search(mergeTrees(root1, root2));
    }

    public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null){
            System.out.println("现在node1和node2都不存在，返回null");
            return null;
        }
        if (root1 != null && root2 != null) {
            System.out.println("现在node1和node2都存在，值为"+root1.val+"和"+root2.val+"，进行合并。。。");
            TreeNode node = new TreeNode(root1.val + root2.val);
            node.left = mergeTrees(root1.left, root2.left);
            node.right = mergeTrees(root1.right, root2.right);
            return node;
        }
        if (root1 != null) {
            System.out.println("现在node1存在值为"+root1.val+",node2不存在，返回node1");
            return root1;
        }
        System.out.println("现在node1不存在node2存在值为"+root2.val+",返回node2");
        return root2;
    }

    //遍历
    public static void search(TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + " ");
        search(node.left);
        search(node.right);
    }
}
